import json

class Solution(object):
    def restoreIpAddresses(self, s):
        def is_valid(segment):
            if len(segment) > 3:
                return False
            if len(segment) > 1 and segment[0] == '0':
                return False
            return 0 <= int(segment) <= 255

        def backtrack(start, parts):
            if len(parts) == 4 and start == len(s):
                result.append('.'.join(parts))
                return
            if len(parts) == 4 or start == len(s):
                return
            for length in range(1, 4):
                if start + length <= len(s):
                    segment = s[start:start + length]
                    if is_valid(segment):
                        parts.append(segment)
                        backtrack(start + length, parts)
                        parts.pop()

        result = []
        backtrack(0, [])
        return result

def main():
    # 直接使用gen.py中定义的5个测试样例
    test_cases = [
        {
            "input": "25525511135",
            "output": ["255.255.11.135", "255.255.111.35"]
        },
        {
            "input": "0000",
            "output": ["0.0.0.0"]
        },
        {
            "input": "101023",
            "output": ["1.0.10.23", "1.0.102.3", "10.1.0.23", "10.10.2.3", "101.0.2.3"]
        },
        {
            "input": "256256256256",
            "output": []
        },
        {
            "input": "1111",
            "output": ["1.1.1.1"]
        }
    ]
    s = Solution()
    for i, case in enumerate(test_cases):
        input_str = case["input"]
        expected_output = case["output"]
        actual_output = s.restoreIpAddresses(input_str)
        print(f"测试样例 {i+1}:")
        print(f'输入："{input_str}"')
        print(f'输出：{actual_output}')
        print(f'期望输出：{expected_output}')
        print(f'测试通过：{sorted(actual_output) == sorted(expected_output)}')
        print()

if __name__ == "__main__":
    main() 